package HighMethod06;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * ClassName:    QuickSortLink
 * Package:    HighMethod06
 * Description:     链表的快排
 * Datetime:    2021/4/18 0018   10:42
 * Author: 沈新源
 */
public class QuickSortLink {

    public static void main(String[] args) {
        MyLinkList myL = new MyLinkList();
        int []arr = {56,78,12,34,90,67,100,45,23,89};
        myL.init_List(arr);     //初始化链表
        myL.Print_List();       //调用函数打印链表

        myL.NiceQuickSort();        //链表的非递归快排
//        myL.QuickSort();        //对链表开始递归快排


        myL.Print_List();       //输出排序结果

    }
}

//单向链表的快排的单向划分
class MyLinkList {
    class ListNode {
        int data;
        public ListNode next;

        public ListNode(){
            data = 0;
            next = null;
        }
        public ListNode(int data){
            this.data = data;
            next = null;
        }
        public ListNode(int data,ListNode narg){
            this.data = data;
            next = narg;
        }
    }

    ListNode head;      //链表头结点

    public MyLinkList(){
        head = null;
    }

    public void init_List(int[] arr) {
        if(arr.length <= 1) return;

        head = new ListNode(arr[0]);
        ListNode p = head;
        for(int i =1;i<arr.length;i++){
            ListNode s = new ListNode(arr[i]);
            p.next = s;
            p = p.next;
        }
    }

    public void Print_List() {
        ListNode p = head;
        while(p!=null){
            System.out.print(p.data+" ");
            p = p.next;
        }
        System.out.println();
    }

    public void QuickSort() {
        QuickPass(head, null);
    }

    void QuickPass(ListNode left, ListNode right) {
        if (left != right) {
            ListNode p = Partition(left, right);
            QuickPass(left, p);
            QuickPass(p.next, right);
        }
    }

    //单向划分
    ListNode Partition(ListNode left, ListNode right) {
        ListNode ip = left, jp = ip.next;
        int tmp = left.data;
        while (jp != right) {
            if (jp.data <= tmp) {
                ip = ip.next;
                Swap_Node(ip, jp);
            }
            jp = jp.next;
        }
        Swap_Node(left, ip);
        return ip;
    }

    private void Swap_Node(ListNode left, ListNode ip) {
        int tmp = left.data;
        left.data = ip.data;
        ip.data = tmp;
    }

    //单链表非递归快排 单向划分
    public void NiceQuickSort() {
        if(head == null||head.next==null) return;

        Queue<ListNode> qu = new LinkedList<>();
        qu.offer(head);
        qu.offer(null);
        while(!qu.isEmpty()){
            ListNode left = qu.poll();
            ListNode right = qu.poll();

            ListNode p = Partition(left,right);     //对链表划分

            if(left!=p){        //###
                qu.offer(left);
                qu.offer(p);
            }

            if(p.next!=right){
                qu.offer(p.next);
                qu.offer(right);
            }

        }
    }
}